package org.gzc.tree;

import java.util.Arrays;

/**
 * @Description: 二叉排序树（二叉查找树）
 * @Author: guozongchao
 * @Date: 2020/8/16 19:11
 */
public class BinarySortTree {
    private Node root;
    class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }

        public void inOrder() {
            if (this.left != null) {
                this.left.inOrder();
            }
            System.out.print(" " + this.value + " ");
            if (this.right != null) {
                this.right.inOrder();
            }
        }
    }

    /**
     * 根据无序数组 创建二叉排序树
     *
     * @param array
     */
    public Node createBST(int[] array) {
        for (int i = 0; i < array.length; i++) {
            insert( array[i]);
        }
        return this.root;
    }

    /**
     * 插入一个值到二叉排序树中(迭代的方式)
     *
     * @param value 要插入的值
     */
    public void insert(int value) {
        //如果根结点为空，则直接添加
        if (root == null) {
            root = new Node(value);
            return ;
        }

        Node p = root;  //p指向当前结点
        Node f = null;
        while (p != null) {   //当 p 指向结点不为空时，由f 指针确定插入的位置的 父结点
            f = p;    //f 指向p当前结点
            if (value < p.value) {  //如果 插入值 比 当前结点值 小，将p 移到当前结点的左子结点
                p = p.left;
            } else {  // 否则，将p 移到当前结点的左子结点
                p = p.right;
            }
        }
        Node node = new Node(value);
        if (value < f.value) {
            f.left = node;
        } else {
            f.right = node;
        }
    }

    /**
     * 查找元素
     *
     * @param root  根结点
     * @param value 需要查找的值
     * @return 返回该结点
     */
    public Node search(Node root, int value) {
        if (root == null) {
            return null;
        } else if (value == root.value) {
            return root;
        } else if (value < root.value) {
            return search(root.left, value);
        } else {
            return search(root.right, value);
        }
    }

    /**
     * 删除元素
     * 分三种情况：
     * (1) 删除叶子结点。直接将其删除
     * (2) 删除单分支结点。删除的结点 P 有左子树或者右子树 时:
     * - 2.1 如果删除结点 P 在左子树，则将删除结点 P 的左子树或右子树直接改为其父结点的左子树;
     * - 2.2 如果删除结点 P 在右子树，则将删除结点 P 的左子树或右子树直接改为其父结点的右子树;
     * (3) 删除双分支结点。删除的结点 P 有左右子树时：
     * - 3.1 可以选择删除结点 P 的左子树中权值最大的结点替换删除结点 P ;
     * --- 3.1.1 将删除结点 P 的左子树 改为 其父结点的 左子树，其右子树 改为 其左子树中权值最大的结点S 的 右子树
     * --- 3.1.2 将删除结点 P 的值 改为 其左子树最大权值的结点S的值，并删除S结点，将S左子树改为 S的父结点Q的右子树
     * - 3.2 也可以选择删除结点 P 的右子树中权值最小的结点替换删除结点 P ;
     *
     * @param value 要删除的值
     * @return 返回根结点
     */
    public Node delete(int value) {
        Node p = root;  //指向需要删除的结点
        Node f = null;  //指向需要删除的结点的父结点
        while (p != null) { //循环找到要删除的结点
            if (value == p.value) {
                break;  //找到,跳出循环
            }
            f = p;
            if (value < p.value) {
                p = p.left;
            } else {
                p = p.right;
            }
        }
        if (p == null) {  //没找到，返回原来的二叉排序树
            return root;
        }
        /**
         * 这里以 p 是否有左子树 来划分 上述 三种情况
         * 如果 p 没有左子树，那么不管 p 的右子树是否为null ，只需要直接将右子树链接到 指定的位置 即可
         * （即 包括 p 是叶子结点 和 只有右分支 情况）
         * 如果 p 有左子树 ，那么只需要找到左子树的权值最大的结点，不管 p 的右子树是否为null ,只需要将p.right链接到权值最大的结点的右链
         * （即，包括了 p只有左分支 和 双分支结点的情况）
         */
        if (p.left == null) {  //如果p没有左子树
            if (f == null) {  //p 恰好是二叉排序树的根结点
                root = p.right;
            } else if (f.left == p) {  //p 是 父结点f的 左结点
                f.left = p.right;   // 将p的右子树 链到 父结点的 左链
            } else { //p 是 父结点f的 右结点
                f.right = p.right;  // 将p的右子树 链到 父结点的 右链
            }
        }else{   // p有左子树

            /**
             * 对应上述的的 3.1.1 方式
             */
            Node s=p.left;
            while (s.right != null) {
                s=s.right;  //从p的左子树开始，一直顺着右子树找到最右的结点
            }
            if(f==null){  //p 恰好是 根结点
                root=p.left;
            }else if(f.left==p){   //p 是 f 的左子结点
                f.left = p.left;
            }else{  //p 是 f 的右子结点
                f.right=p.left;
            }
            s.right=p.right;
        }
        return root;
    }


    //中序遍历
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        root.inOrder();
    }

    public static void main(String[] args) {
        int[] array = new int[]{15, 7, 21, 9, 6, 43, 10, 18, 20, 11,19,13,56,16,12};
        System.out.println("原始数组：" + Arrays.toString(array));
        BinarySortTree bts = new BinarySortTree();
        Node bstRoot = bts.createBST(array);
        System.out.print("二叉排序树中序遍历：");
        bts.inOrder(bstRoot);
        Node result = bts.search(bstRoot, 11);
        System.out.println("\n查找结果：" + result.value);
        Node delete = bts.delete(15);
        System.out.print("删除后结果：");
        bts.inOrder(delete);
    }
}